package com.zql.LeetCode;

/**
 * 前缀和数组的应用
 * Created By ShuHua on 2021/8/20.
 */
public class NumArray_560 {

    private int[] arr;

    public NumArray_560(int[] nums) {
        int n = nums.length;
        int[] newArr = new int[n+1];
        for(int i=0;i<n;i++){
            newArr[i+1]=newArr[i]+nums[i];
        }
        this.arr=newArr;
    }

    /**
     * 303. 区域和检索 - 数组不可变
     * @param left
     * @param right
     * @return
     */
    public int sumRange(int left, int right) {
        if(left<0||right>arr.length+1) return -1;
        return arr[right+1]-arr[left];
    }

    /**
     * 560. 和为K的子数组
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count=0;
        int[] arr = new int[n+1];
        for(int i=0;i<n;i++){
            arr[i+1]=arr[i]+nums[i];
        }
        //这里不能减2,因为子数组可以只有一个元素
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]-arr[i]==k){
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 错误提交，原因，错认为单独一个元素不能算做和
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum_error(int[] nums, int k) {
        int n = nums.length;
        int count=0;
        int[] arr = new int[n+1];
        for(int i=0;i<n;i++){
            arr[i+1]=arr[i]+nums[i];
        }
        //这里不能减2
        for(int i=0;i<arr.length-2;i++){
            for(int j=i+2;j<arr.length;j++){
                if(arr[j]-arr[i]==k){
                    count++;
                }
            }
        }
        return count;
    }
}
